#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int missingInteger(vector<int>& nums) {
        int sum = nums[0];
        for (int i = 1; i < nums.size(); i++)
        {
            if (nums[i] != nums[i - 1] + 1)
            {
                break;
            }
            sum += nums[i];
        }

        sort(nums.begin(), nums.end());
        auto it = lower_bound(nums.begin(), nums.end(), sum);
        while (it != nums.end() && *it == sum)
        {
            sum++;
            it++;
            it = lower_bound(it, nums.end(), sum);
        }

        return sum;
    }
};